package LinearList;

import java.util.Scanner;

public class LinkList implements IList{
    // 单链表的头指针
    public Node head;
    // 构造函数初始化头结点
    public LinkList() {
        head = new Node();
    }
    // 构造函数构造长度n的单链表
    public LinkList(int n, boolean Order) throws Exception {
        this();
        if(Order){
            create1(n);
        }else {
            create2(n);
        }
    }

    // 头插法
    public void create1(int n) throws Exception {
        Scanner sc = new Scanner(System.in);
        for(int i=0; i<n ; i++){
            insert(0, sc.next());
        }
    }

    // 尾插法
    public void create2(int n) throws Exception {
        Scanner sc = new Scanner(System.in);
        for(int i=0; i<n; i++){
            insert(length(), sc.next());
        }
    }

    // 链表置为空
    public void clear(){
        head.data = null;
        head.next = null;
    }

    // 判断链表是否为空
    public boolean isEmpty(){
        return head.next == null;
    }

    // 返回链表长度
    public int length(){
        Node p = head.next;
        int length = 0;
        while(p!= null){
            p = p.next;
            length++;
        }
        return length;
    }

    // 返回索引为i的元素
    // 位序查找法
    public Object get(int i) throws Exception {
        // p指向单链表的首节点
        Node p = head.next;
        int j;
        // 从首节点开始向后查找，直到p指向第i个结点或者p为null
        for(j=0; j<i && p!=null; j++){
            p = p.next;
        }
        // 如果查找的索引 比链表最大的索引大就抛出异常
        // 如果 p 指向的为null代表链表已经为空了 抛出异常
        if( j>i || p==null){
            throw new Exception("索引为"+i+"的数据元素不存在");
        }
        return p.data;

    }

    // 在索引为i的位置插入x元素
    public void insert(int i, Object x) throws Exception {
        Node p = head;
        int j = -1;
        // 寻找前驱
        while(p!=null && j<i-1){
            p = p.next;
            j++;
        }
        // 当 j > i-1 说明没有找到前驱
        // p==null 说明到了尾结点
        if(j>i-1 || p==null){
            throw new Exception("插入位置不合法");
        }
        Node s = new Node(x);
        // 如果插入位置为头结点
        if(i==0){
            // 新节点指向 当前头结点
            s.next = head;
            // 头结点变为 当前节点
            head = s;
        }else {
            // 新节点 指向i的节点的下一个节点
            s.next = p.next;
            // p的下一个节点 指向新节点上
            p.next = s;
        }
    }

    // 删除第i个元素
    public void remove(int i) throws Exception {
        Node p = head;
        int j = -1;
        // 寻找第i个结点的前驱结点
        while(p!=null && j<i-1){
            p = p.next;
            j++;
        }
        // 抛出异常
        if(j>i-1 || p.next == null){
            throw new Exception("删除位置不合法");
        }else{
            // 合理就把 p的指针 指向删除结点的后结点（跳过该节点）
            p.next = p.next.next;
        }
    }



    // 返回元素x首次出现的位序号
    public int indexOf(Object x) {
        Node p =head.next;
        int j= 0;
        // 如果p不为null 代表这个结点还不是尾结点
        // 所以可以持续进行循环直到 p为尾结点 或者 p和x相等 否则持续前进 并且索引+1
        while(p!=null && !p.equals(x)){
            p = p.next;
            j++;
        }
        // 因为p为null而结束 并不是真的找到了该元素
        if(p!=null){
            return j;
        }else{
            return -1;
        }
    }

    // 展示数据
    public void display() {
        Node p = head.next;
        while(p!=null){
            System.out.print(p.data + " ");
            p = p.next;
        }
    }


}
